
/*
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * SPDX-License-Identifier: GPL-3.0+
 * License-Filename: LICENSE
 * Copyright tuxsee authors
 */

/* modified from GNU GCC versions splay tree database */

/* A splay-tree datatype.
   Copyright (C) 1998 Free Software Foundation, Inc.
   Contributed by Mark Mitchell

This file is part of GNU CC.

GNU CC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU CC is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

/* For an easily readable description of splay-trees, see:

     Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
     Algorithms.  Harper-Collins, Inc.  1991.

  verified it is no problem to run this splay tree nested
  inside another splay tree, nested inside a splay tree etc.

  splay is fast because it is based on the real-world observation
  that a search in data is done with a key the next search is often
  with a similar key value so splay changes root of the tree everytime.
*/

/*
 * Today a Linux kernel has 128 PiB of virtual address space
 * and 4 PiB of physical address space in ram memory.
 * Linux wrote "This ought to be enough for anybody."
 * A TiB, or Tebibyte, is approximately 1.1 Terabytes.
 */

#include "config.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>

#include "splay-tree.h"
#include "main.h"
#include "mem.h"

/* if set print memory usage --debug 0/1/2 or -D 0/1/2 */
int option_memlog = 0;		/* moved from options.c */

/* if set run memory tracker and usage */
int option_memtrack = 1;	/* moved from options.c */

/* main malloc/free wrapper of the program except for the memory
 * used by the gtk gui library routines and other linked libs.
 * This has a memory tracking feature so the program does
 * constantly check for memory leakage and prints an error message.
 * This message is a list of pointers not free()'ed with number
 * of bytes involved and a total leakage summary.
 * For more info then valgrind software is used.
 * It is critical that the program assumes malloc() returns zero'ed
 * memory similar as calloc() does. free()'ed pointers are set to 0.
 */

/* A customized GNU GCC splay() is used for memory tracking. */

/* A splay-tree datatype.
   Copyright (C) 1998 Free Software Foundation, Inc.
   Contributed by Mark Mitchell

This file is part of GNU CC.

GNU CC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU CC is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

/* For an easily readable description of splay-trees, see:

     Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
     Algorithms.  Harper-Collins, Inc.  1991.

   The major feature of splay trees is that all basic tree operations
   are amortized O(log n) time for a tree with n nodes.

 */

/* how many bytes can a splay key to index on have max. */
typedef void *mt_splay_tree_key;

/* how many bytes can a splay value have max. */
typedef size_t mt_splay_tree_value;

/* The nodes in the splay tree.  */
struct mt_splay_tree_node_n {
	/* The key.  */
	mt_splay_tree_key key;

	/* The value.  */
	mt_splay_tree_value value;

	/* The left and right children, respectively.  */
	struct mt_splay_tree_node_n *left;
	struct mt_splay_tree_node_n *right;
};

/* The splay tree itself.  */
struct mt_splay_tree_t {
	/* The root of the tree.  */
	struct mt_splay_tree_node_n *root;
};

/* Forward declaration for a tree.  */
typedef struct mt_splay_tree_t *mt_splay_tree;

/* Forward declaration for a node in the tree.  */
typedef struct mt_splay_tree_node_n *mt_splay_tree_node;

/* malloc/free counters 64-bits */
static unsigned long long mt_malloccount = 0;
static unsigned long long mt_freecount = 0;

/* malloc/free counters 64-bits */
static unsigned long long malloccount = 0;
static unsigned long long freecount = 0;
static unsigned long long realloccount = 0;

/* the splay with data which ptr's are malloc'ed */
static mt_splay_tree mt = (mt_splay_tree) 0;

/* to compare pointers in c is a problem. cast to intptr_t seem to work. */
static int mt_splay_tree_compare_pointers(mt_splay_tree_key k1, mt_splay_tree_key k2)
{
	/* (0==0) */
	if ((k1 == (mt_splay_tree_key) 0) && (k2 == (mt_splay_tree_key) 0)) {
		return (0);
	}
	if ((intptr_t) k1 < (intptr_t) k2) {
		return ((int)-1);
	} else if ((intptr_t) k1 > (intptr_t) k2) {
		return (1);
	} else {
		return (0);
	}
}

static mt_splay_tree_node mt_splay_tree_min(mt_splay_tree sp)
{
	mt_splay_tree_node n = (mt_splay_tree_node) 0;

	/* <nil> splaytree */
	if (sp == (mt_splay_tree) 0) {
		return ((mt_splay_tree_node) 0);
	}

	/* no data */
	if (sp->root == (mt_splay_tree_node) 0) {
		return ((mt_splay_tree_node) 0);
	}

	n = sp->root;

	/* scan l */
	while (n->left) {
		n = n->left;
	}

	return ((mt_splay_tree_node) n);
}

/* return 1 if splay tree has data, otherwise 0 */
static int mt_splay_tree_has_data(mt_splay_tree sp)
{
	if (sp == (mt_splay_tree) 0) {
		return (0);
	}
	if (sp->root) {
		return (1);
	} else {
		return (0);
	}
}

/* create new tree */
static mt_splay_tree mt_splay_tree_new(void)
{
	mt_splay_tree sp = (mt_splay_tree) 0;

	sp = (mt_splay_tree) malloc(sizeof(struct mt_splay_tree_t));

	if (sp == (mt_splay_tree) 0) {
		return ((mt_splay_tree) 0);
	}

	memset(sp, 0, sizeof(struct mt_splay_tree_t));

	/* a barrier which does not get optimized away */
	__asm__("");

	/* for clang, llvm and gcc compilers */
#ifdef __GNUC__
	/* barrier the optimizer should not optimize away */
	__asm__ __volatile__(""::"r"(sp):"memory");
#endif
	/* for intel ecc compiler */
#ifdef __ECC
	__memory_barrier();
#endif

	sp->root = (mt_splay_tree_node) 0;

	return ((mt_splay_tree) sp);
}

static void mt_rotate_left(mt_splay_tree_node * pp, mt_splay_tree_node p, mt_splay_tree_node n)
{
	mt_splay_tree_node tmp = (mt_splay_tree_node) 0;
	tmp = n->right;
	n->right = p;
	p->left = tmp;
	*pp = n;
	return;
}

/* Rotate the edge joining the right child N with its parent P.  PP is the
   grandparents' pointer to P.  */
/* no inline because of gdb debug */
static void mt_rotate_right(mt_splay_tree_node * pp, mt_splay_tree_node p, mt_splay_tree_node n)
{
	mt_splay_tree_node tmp = (mt_splay_tree_node) 0;
	tmp = n->left;
	n->left = p;
	p->right = tmp;
	*pp = n;
	return;
}

/* Splay SP around KEY.  */

static void mt_splay_tree_splay(mt_splay_tree sp, mt_splay_tree_key key)
{
	int cmp1 = 0;
	int cmp2 = 0;
	mt_splay_tree_node n = (mt_splay_tree_node) 0;
	mt_splay_tree_node c = (mt_splay_tree_node) 0;

	/* <nil> splaytree */
	if ((mt_splay_tree) 0 == sp) {
		return;
	}

	/* no data */
	if (sp->root == (mt_splay_tree_node) 0) {
		return;
	}

	do {
		/* init */
		cmp1 = 0;
		cmp2 = 0;

		n = (mt_splay_tree_node) 0;
		c = (mt_splay_tree_node) 0;

		n = sp->root;

		cmp1 = mt_splay_tree_compare_pointers(key, n->key);

		/* Found.  */
		if (cmp1 == 0) {
			return;
		}

		/* Left or right?  If no child, then we're done.  */
		if (cmp1 < 0) {
			c = n->left;
		} else {
			c = n->right;
		}

		if (c == (mt_splay_tree_node) 0) {
			return;
		}

		/* Next one left or right?  If found or no child, we're done
		   after one rotation.  */
		cmp2 = mt_splay_tree_compare_pointers(key, c->key);

		if ((cmp2 == 0) || ((cmp2 < 0) && (c->left == (mt_splay_tree_node) 0))
		    || ((cmp2 > 0) && (c->right == (mt_splay_tree_node) 0))) {
			if (cmp1 < 0) {
				mt_rotate_left(&sp->root, n, c);
			} else {
				mt_rotate_right(&sp->root, n, c);
			}
			return;
		}

		/* Now we have the four cases of double-rotation.  */
		if ((cmp1 < 0) && (cmp2 < 0)) {
			mt_rotate_left(&n->left, c, c->left);
			mt_rotate_left(&sp->root, n, n->left);
		} else if ((cmp1 > 0) && (cmp2 > 0)) {
			mt_rotate_right(&n->right, c, c->right);
			mt_rotate_right(&sp->root, n, n->right);
		} else if ((cmp1 < 0) && (cmp2 > 0)) {
			mt_rotate_right(&n->left, c, c->right);
			mt_rotate_left(&sp->root, n, n->left);
		} else if ((cmp1 > 0) && (cmp2 < 0)) {
			mt_rotate_left(&n->right, c, c->left);
			mt_rotate_right(&sp->root, n, n->right);
		} else {
			/* this actually generates assembly sourcecode. */
		}
	}
	while (1);

	return;
}

static mt_splay_tree_node mt_splay_tree_successor(mt_splay_tree sp, mt_splay_tree_key key)
{
	int comparison = 0;
	mt_splay_tree_node node = (mt_splay_tree_node) 0;

	if (sp == (mt_splay_tree) 0) {
		return ((mt_splay_tree_node) 0);
	}

	/* If the tree is empty, there is certainly no successor.  */
	if (sp->root == (mt_splay_tree_node) 0) {
		return ((mt_splay_tree_node) 0);
	}

	/* Splay the tree around KEY.  That will leave either the KEY
	   itself, its predecessor, or its successor at the root.  */
	mt_splay_tree_splay(sp, key);

	comparison = mt_splay_tree_compare_pointers(sp->root->key, key);

	/* If the successor is at the root, just return it.  */
	if (comparison > 0) {
		return ((mt_splay_tree_node) sp->root);
	}

	/* Otherwise, find the leftmost element of the right subtree.  */
	node = sp->root->right;

	if (node) {
		while (node->left) {
			node = node->left;
		}
	}

	return ((mt_splay_tree_node) node);
}

static void mt_splay_tree_insert(mt_splay_tree sp, mt_splay_tree_key key, mt_splay_tree_value value)
{
	int comparison = 0;
	mt_splay_tree_node node = (mt_splay_tree_node) 0;

	if (sp == (mt_splay_tree) 0) {
		/* nothing todo */
		return;
	}

	/* balance tree, possibly without any data then sp->root is 0 */
	mt_splay_tree_splay(sp, key);

	/* if there is data */
	if (sp->root) {
		comparison = mt_splay_tree_compare_pointers(sp->root->key, key);
	}

	if (sp->root && (comparison == 0)) {
		sp->root->value = value;
	} else {
		/* Create a new node, and insert it at the root.  */
		node = (mt_splay_tree_node) malloc(sizeof(struct mt_splay_tree_node_n));

		if (node == (mt_splay_tree_node) 0) {
			return;
		}

		memset(node, 0, sizeof(struct mt_splay_tree_node_n));

		/* a barrier which does not get optimized away */
		__asm__("");

		/* for clang, llvm and gcc compilers */
#ifdef __GNUC__
		/* barrier the optimizer should not optimize away */
		__asm__ __volatile__(""::"r"(node):"memory");
#endif
		/* for intel ecc compiler */
#ifdef __ECC
		__memory_barrier();
#endif

		node->key = key;
		node->value = value;

		if (sp->root == (mt_splay_tree_node) 0) {
			node->left = (mt_splay_tree_node) 0;
			node->right = (mt_splay_tree_node) 0;
		} else if (comparison < 0) {
			node->left = sp->root;
			node->right = node->left->right;
			node->left->right = (mt_splay_tree_node) 0;
		} else {
			node->right = sp->root;
			node->left = node->right->left;
			node->right->left = (mt_splay_tree_node) 0;
		}

		sp->root = node;
	}

	return;
}

static void mt_splay_tree_delete_helper(mt_splay_tree sp, mt_splay_tree_node node)
{

	/* return if nothing todo */
	if (node == (mt_splay_tree_node) 0) {
		return;
	}

	/* recurse */
	if (node->left) {
		/* avoid needless recurs */
		mt_splay_tree_delete_helper(sp, node->left);
	}

	if (node->right) {
		/* avoid needless recurs */
		mt_splay_tree_delete_helper(sp, node->right);
	}

	/* clear the pointers in the struct, then memory blocks are not reachable anymore and valgrind checks for that. */
	node->left = (mt_splay_tree_node) 0;
	node->right = (mt_splay_tree_node) 0;

	free((void *)node);

	return;
}

static void mt_splay_tree_delete(mt_splay_tree sp)
{

	if (sp == (mt_splay_tree) 0) {
		return;
	}

	if (sp->root) {
		mt_splay_tree_delete_helper(sp, sp->root);
	}

	/* wipe the pointers in the struct to make valgrind happy */
	sp->root = (mt_splay_tree_node) 0;

	free((void *)sp);

	return;
}

static mt_splay_tree_node mt_splay_tree_lookup(mt_splay_tree sp, mt_splay_tree_key key)
{

	if (sp == (mt_splay_tree) 0) {
		/* no tree, should not happen */
		return ((mt_splay_tree_node) 0);
	}

	if (sp->root == (mt_splay_tree_node) 0) {
		/* no data in tree */
		return ((mt_splay_tree_node) 0);
	}

	if (mt_splay_tree_compare_pointers(sp->root->key, key) == 0) {
		/* found */
		return ((mt_splay_tree_node) sp->root);
	}

	/* */
	mt_splay_tree_splay(sp, key);

	if (sp->root == (mt_splay_tree_node) 0) {
		/* no data in tree */
		return ((mt_splay_tree_node) 0);
	}

	if (mt_splay_tree_compare_pointers(sp->root->key, key) == 0) {
		/* found */
		return ((mt_splay_tree_node) sp->root);
	} else {
		/* not found */
		return ((mt_splay_tree_node) 0);
	}
}

static void mt_splay_tree_remove(mt_splay_tree sp, mt_splay_tree_key key)
{
	mt_splay_tree_node node = (mt_splay_tree_node) 0;
	mt_splay_tree_node left = (mt_splay_tree_node) 0;
	mt_splay_tree_node right = (mt_splay_tree_node) 0;

	/* */
	mt_splay_tree_splay(sp, key);

	if (sp->root == (mt_splay_tree_node) 0) {
		printf("%s(): nil root at free pointer %p\n", __FUNCTION__, (void *)key);
		fflush(stdout);
		return;
	}

	/* */
	if (mt_splay_tree_compare_pointers(sp->root->key, key)) {
		printf("%s(): free pointer %p not found\n", __FUNCTION__, (void *)key);
		fflush(stdout);
		return;
	}

	node = sp->root;
	left = sp->root->left;
	right = sp->root->right;

	/* One of the children is now the root.  Doesn't matter much
	   which, so long as we preserve the properties of the tree.  */
	if (left) {
		sp->root = left;
		/* If there was a right child as well, hang it off the
		   right-most leaf of the left child.  */
		if (right) {
			while (left->right) {
				left = left->right;
			}
			left->right = right;
		}
	} else {
		sp->root = right;
	}

	/* free() node itself and wipe the pointers */
	node->left = (mt_splay_tree_node) 0;
	node->right = (mt_splay_tree_node) 0;
	free((void *)node);
	node = (mt_splay_tree_node) 0;

	return;
}

static void memtrack_add_malloc(void *p, size_t n)
{
	mt_splay_tree_node spn = (mt_splay_tree_node) 0;

	if (mt == (mt_splay_tree) 0) {
		mt = mt_splay_tree_new();
		/* malloc/free counters 64-bits */
		mt_malloccount = 0;
		mt_freecount = 0;
	}

	spn = mt_splay_tree_lookup(mt, (mt_splay_tree_key) p);

	if (spn) {
		printf("%s(): memory location %p already in use\n", __FUNCTION__, (void *)p);
		fflush(stdout);
		return;
	}

	mt_splay_tree_insert(mt, (mt_splay_tree_key) p, (mt_splay_tree_value) n);

	mt_malloccount = (mt_malloccount + 1);

	return;
}

static int memtrack_check_free(void *p)
{
	mt_splay_tree_node spn = (mt_splay_tree_node) 0;

	/* shouldnothappen */
	if (mt == (mt_splay_tree) 0) {
		return (0);
	}

	spn = mt_splay_tree_lookup(mt, (mt_splay_tree_key) p);

	if (spn) {
		return (1);
	} else {
		return (0);
	}
}

static void memtrack_run_free(void *p)
{

	/* shouldnothappen */
	if (mt == (mt_splay_tree) 0) {
		printf("%s(): nil mt\n", __FUNCTION__);
		fflush(stdout);
		return;
	}

	mt_splay_tree_remove(mt, (mt_splay_tree_key) p);

	mt_freecount = (mt_freecount + 1);

	return;
}

/* malloc wrapper */
void *mymalloc(size_t n, const char *func, int line)
{
	char *ptr2 = (char *)0;
	long long unsigned nn = 0;
	void *ptr = NULL;
	if (n == 0) {
		printf("%s(): malloc(0) at %s() line %d\n", __FUNCTION__, func, line);
		fflush(stdout);
		return (NULL);
	}
	ptr = malloc(n);
	if (ptr) {
		if (option_memtrack) {
			memtrack_add_malloc(ptr, n);
		}
		if (option_memlog > 1) {
			printf("%p\t_m_\t%s() line %d\n", (void *)ptr, func, line);
			fflush(stdout);
		}
		ptr2 = ptr;
		nn = (unsigned long long)n;
		while (nn) {
			*ptr2 = 0;
			ptr2++;
			nn--;
		}
		malloccount++;
		/* a barrier which does not get optimized away */
		__asm__("");

		/* for clang, llvm and gcc compilers */
#ifdef __GNUC__
		/* barrier the optimizer should not optimize away */
		__asm__ __volatile__(""::"r"(ptr):"memory");
#endif
		/* for intel ecc compiler */
#ifdef __ECC
		__memory_barrier();
#endif
	} else {
		/* malloc() returned NULL */
	}
	return (ptr);
}

/* free wrapper */
void myfree(void *ptr, const char *func, int line)
{
	if (option_memlog > 1) {
		printf("%p\t_f_\t%s() line %d\n", (void *)ptr, func, line);
		fflush(stdout);
	}
	if (ptr) {
		if (option_memtrack) {
			if (memtrack_check_free(ptr)) {
				memtrack_run_free(ptr);
				/* free (ptr);
				 * this does free() and sets the pointer to 0x00 with glibc
				 */
				ptr = realloc(ptr, 0);
				freecount++;
			} else {
				printf("%s(): ptr %p is unknown\n", __FUNCTION__, (void *)ptr);
				fflush(stdout);
				/* do not free() to avoid double-free or free of random pointer */
			}
		} else {
			/* free (ptr);
			 * this does free() and sets the pointer to 0x00 with glibc
			 */
			ptr = realloc(ptr, 0);
			freecount++;
		}
	} else {
		printf("%s(): nil pointer at %s() line %d\n", __FUNCTION__, func, line);
		fflush(stdout);
	}

	return;
}

/* realloc wrapper */
void *myrealloc(void *ptr, size_t size, const char *func, int line)
{
	void *ptr2 = NULL;
	ptr2 = realloc(ptr, size);
	if (ptr2) {
		if (option_memlog > 1) {
			printf("%llu\t_r_\t%s() line %d\n", (unsigned long long)ptr2, func, line);
			fflush(stdout);
		}
		malloccount++;
		realloccount++;
	}

	return (ptr2);
}

/* statistics */
void mymemstats(void)
{
	if (option_memlog) {
		printf("%s(): malloc/free count is %llu:%llu delta=%llu (%llu realloc)\n", __FUNCTION__, malloccount, freecount,
		       (malloccount - freecount), realloccount);
		fflush(stdout);
	}
	if (malloccount != freecount) {
		printf
		    ("%s(): malloc/free count is %llu:%llu delta=%llu (%llu realloc) possible memory leakage\n",
		     __FUNCTION__, malloccount, freecount, (malloccount - freecount), realloccount);
		fflush(stdout);
	}
	malloccount = 0;
	freecount = 0;
	realloccount = 0;
	return;
}

void myfinalmemcheck(void)
{
	mt_splay_tree_node spn = (mt_splay_tree_node) 0;
	void *ptr = (void *)0;
	unsigned long long nb = (unsigned long long)0;
	unsigned long long nbtotal = (unsigned long long)0;

	if (option_memtrack) {

		if (mt == (mt_splay_tree) 0) {
			printf("%s(): no tracking data\n", __FUNCTION__);
			return;
		}

		if (mt_splay_tree_has_data(mt)) {
			printf
			    ("%s(): memory leakage %llu bytes in use after %llu malloc() and %llu free() (use valgrind to check)\n",
			     __FUNCTION__, ntotalmemuse(), ntotalmallocs(), ntotalfree());
			fflush(stdout);
			/* there is data and possible memleak */
			nbtotal = 0;
			spn = mt_splay_tree_min(mt);
			while (spn) {
				ptr = (void *)spn->key;
				nb = (unsigned long long)spn->value;
				nbtotal = (nbtotal + nb);
				printf("%s(): pointer %p to %llu bytes is not free()'ed and total memory leakage is %llu bytes\n",
				       __FUNCTION__, (void *)ptr, nb, nbtotal);
				fflush(stdout);
				spn = mt_splay_tree_successor(mt, spn->key);
			}
		}

		mt_splay_tree_delete(mt);
	}

	return;
}

/* */
unsigned long long ntotalmallocs(void)
{
	return (mt_malloccount);
}

/* */
unsigned long long ntotalfree(void)
{
	return (mt_freecount);
}

/* */
unsigned long long ntotalmemuse(void)
{
	unsigned long long nb = (unsigned long long)0;
	unsigned long long nbtotal = (unsigned long long)0;
	mt_splay_tree_node spn = (mt_splay_tree_node) 0;

	if (mt_splay_tree_has_data(mt)) {
		/* there is data and possible memleak */
		nbtotal = 0;
		spn = mt_splay_tree_min(mt);
		while (spn) {
			nb = (unsigned long long)spn->value;
			nbtotal = (nbtotal + nb);
			spn = mt_splay_tree_successor(mt, spn->key);
		}
	}
	return (nbtotal);
}

/* end */
